package algocasts;

public class P79_LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length, max = 1;
        int[] d = new int[n];
        d[0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int cur = nums[i] > nums[j] ? d[j] + 1 : 1;
                d[i] = Math.max(d[i], cur);
            }
            max = Math.max(max, d[i]);
        }
        return max;
    }

    private int binarySearchInsertPosition(int[] d, int len, int x) {
        int low = 0, high = len - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (x < d[mid]) high = mid - 1;
            else if (x > d[mid]) low = mid + 1;
            else return mid;
        }
        return low;
    }

    public int lengthOfLISBinarySearch(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length, len = 0;
        int[] d = new int[n];
        for (int x : nums) {
            int i = binarySearchInsertPosition(d, len, x);
            d[i] = x;
            if (i == len) ++len;
        }
        return len;
    }

}
